/**
 * 快速排序算法
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LEN 100000
#define MAX 1000

void randArray(int v[], int n, int max);
void quicksort(int v[], int left, int right);
void printArray(int v[], int n, int width);
int compare(const void* a, const void* b);

int main() {
    int v[LEN];
    clock_t time_taken;
    randArray(v, LEN, MAX); 
    printf("quicksort, before: \n");
    //printArray(v, LEN, 20);
    printf("quicksort, after: \n");
    time_taken = clock();
    quicksort(v, 0, LEN-1);
    time_taken = clock() - time_taken;
    //printArray(v, LEN, 20);
    printf("time: %lu clocks\n", time_taken);

    // 标准库中的qsort
    randArray(v, LEN, MAX); 
    printf("qsort, before: \n");
    //printArray(v, LEN, 20);
    time_taken = clock();
    qsort(v, LEN, sizeof(int), compare);
    time_taken = clock() - time_taken;
    printf("qsort, after: \n");
    //printArray(v, LEN, 20);
    printf("time: %lu clocks\n", time_taken);

    return 0;
}

void quicksort(int v[], int left, int right) {
    int i, j, t, temp;
    if (left > right)
        return;
    temp = v[left];
    i = left;
    j = right;
    while (i != j) {
        while (v[j] >= temp && i < j)
            j--;
        while (v[i] <= temp && i < j)
            i++;
        if (i < j)
            v[i] ^= v[j], v[j] ^= v[i], v[i] ^= v[j];
    }
    v[left] = v[i];
    v[i] = temp;

    quicksort(v, left, i-1);
    quicksort(v, i+1, right);
}

void randArray(int v[], int n, int max) {
    for (int i = 0; i < n; i++) {
        v[i] = rand() % max;
    }
}

void printArray(int v[], int n, int width) {
    for (int i = 0; i < n; i++)
        printf("%6d%c", v[i], (i%width == width-1 || i == n-1) ? '\n' : ' ');
}

int compare(const void* a, const void* b) {
    int arg1 = *(const int*)a;
    int arg2 = *(const int*)b;

    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}
